// 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
// 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
// 必须原地修改，只允许使用额外常数空间。
// 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

// 暴露接口
const nextPermutation = function (nums: number[]): number[] {
    // 安全检测
    if (nums.length < 2) {
        return nums;
    }
    let left: number = nums.length - 2;
    let right: number = nums.length - 1;
    // 注意这里只能是等于，考虑极端情况[1,1,1,1],这个循环的结果要保证最大排列序列结束后left指针要指向-1
    while (left >= 0 && nums[left] >= nums[left + 1]) {
        left--;
    }
    // 如果这个数组不是递减序列
    if (left >= 0) {
        // 注意细节，这里只能是小于等于，不然会造成无用交换
        while (nums[right] <= nums[left]) {
            right--;
        }
        nextPermutation_swap(nums, left, right);
    }
    // 默认操作，将left指针后的结果重置为从左往右的升序，升序排列就是最小的排列
    left = left + 1;
    right = nums.length - 1;
    while (left < right) {
        nextPermutation_swap(nums, left, right);
        left++;
        right--;
    }
    return nums;
};
// 交换函数
function nextPermutation_swap(arr: number[], index1: number, index2: number) {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
}

nextPermutation([1, 1])


// 这道题目是一道比较难想到的数学题，算法上并不是很直观。
// 我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。
// 如何将这些数字重新排列，以得到下一个更大的整数。
// 我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。
// 因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。
// 我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。
// 为了满足这个要求，我们需要：
// 1.在尽可能靠右的低位进行交换，需要从后向前查找
// 2.将一个 尽可能小的「大数」 与前面的「小数」交换。
// 3.将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。
// 此外，也要额外注意这里的几个循环判断的条件书写，第一个循环我们是需要保证最大序列下left指针一定得指向-1
// 第二个循环我们则需要保证，right指针交换过来的数位一定是大于left指针的，不然就是无用交换了
// 最后的重置也一定要记得，容易遗漏，因为我们需要保证后续的数字一定得是从右往左升序而非降序